package com.spirng.leetcode.day05;

import java.util.*;

public class Test239 {
    public static void main(String[] args) {
        Test239 test239 = new Test239();
        test239.maxSlidingWindow(new int[]{1,3,1,2,0,5},3);
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
           int [] arr= new int[nums.length-k+1];
        MyQueue deque = new MyQueue();
        for (int i = 0; i <k; i++) {
            deque.add(nums[i]);
        }
        arr[0]=deque.getMax();
        int count=1;
        for (int i=k;i< nums.length;i++){
            deque.pop(nums[i-k]);
            deque.add(nums[i]);
            arr[count++]=deque.getMax();
        }
        return arr;
    }
    class MyQueue {
        Deque<Integer> deque = new LinkedList<Integer>();


        public void pop(int val) {
            if (!deque.isEmpty() && val == deque.peekFirst()) {
                deque.poll();
            }
        }

        public void add(int val) {
            while (!deque.isEmpty() && val > deque.peekLast()) {
                deque.removeLast();
            }
            deque.add(val);
        }

        public int getMax() {
            return deque.peek();
        }
    }
}
